package com.ljy.my_study.leetcode.跳跃游戏IV;

import java.util.*;

/**
 * @Description:
 * @Author: li.junying
 * @date: 2022-01-21 10:52
 */
public class TestMain2 {

//    bfs 從0出發，一個個可能的步驟加入queue中
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> map=new HashMap<>();
        int len=arr.length;
        for(int i=0;i<len;i++){
            List<Integer> list= map.getOrDefault(arr[i],new ArrayList<>());
            list.add(i);
            map.put(arr[i],list);
        }
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,0});
        Set<Integer> visited=new HashSet<>();
        visited.add(0);
        while(!queue.isEmpty()){
            int[] idxStep=queue.poll();
            int index=idxStep[0];
            int step=idxStep[1];
            if(index==len-1){
                return step;
            }
            step++;
            if(map.containsKey(arr[index])){
                List<Integer> list=map.get(arr[index]);
                for(int nextIndex:list){
                    if(visited.add(nextIndex)){
                        queue.offer(new int[]{nextIndex,step});
                    }
                }
                map.remove(arr[index]);
            }
            if(index+1<len&&visited.add(index+1)){
                queue.offer(new int[]{index+1,step});
            }
            if(index-1>=0&&visited.add(index-1)){
                queue.offer(new int[]{index-1,step});
            }
        }
        return -1;
    }
}
